Here is a study guide for Chapter 9: Counting and Probability, based on the provided excerpts:

Chapter 9: Counting and Probability

This chapter introduces fundamental concepts and techniques for counting discrete objects and determining the likelihood of events. The central issue in counting problems is often identifying precisely what needs to be counted.

Section 9.1: Introduction to Probability (pp. 564-573)

• Overview: This section lays the groundwork for probability by defining key terms such as sample space (the set of all possible outcomes of a random process or experiment) and event (a subset of the sample space). It focuses on the equally likely case, where each outcome in the sample space has the same chance of occurring. In such cases, the probability of an event is the ratio of the number of outcomes in the event to the total number of outcomes. The section also discusses counting elements of lists, sublists, and one-dimensional arrays.

• Important Theorems and Equations:

  • Theorem 9.1.1: If $m$ and $n$ are integers and $m \le n$, then there are $n - m + 1$ integers from $m$ to $n$ inclusive.
  • Probability of an Event (Equally Likely Outcomes): $P(E) = \frac{N(E)}{N(S)}$, where $E$ is the event, $S$ is the sample space, $N(E)$ is the number of outcomes in $E$, and $N(S)$ is the total number of outcomes in $S$.

Section 9.2: Possibility Trees and the Multiplication Rule (pp. 573-589)

• Overview: This section introduces possibility trees as a visual tool for analyzing multi-step operations. The core concept is the multiplication rule, which provides a way to count the total number of outcomes when an operation is performed in a sequence of steps. The number of ways to perform each step must be constant regardless of how previous steps were performed for the multiplication rule to be directly applicable. The section also introduces the concept of permutations, which are orderings of objects.

• Important Theorems and Equations:

  • Theorem 9.2.1 (The Multiplication Rule): If an operation consists of $k$ steps, and the $i$-th step can be performed in $n_i$ ways (regardless of previous steps), then the entire operation can be performed in $n_1 \times n_2 \times \dots \times n_k$ ways.
  • Theorem 9.2.3 (Number of r-Permutations): The number of $r$-permutations of a set of $n$ elements, denoted by $P(n, r)$, where $1 \le r \le n$, is given by: $P(n, r) = n(n-1)(n-2) \dots (n - r + 1)$ (first version) or $P(n, r) = \frac{n!}{(n-r)!}$ (second version)

Section 9.3: Counting Elements of Disjoint Sets: The Addition Rule (pp. 589-604)

• Overview: This section focuses on counting elements in the union, difference, and intersection of sets. The addition rule is introduced for counting the number of elements in the union of mutually disjoint sets. The difference rule allows calculating the number of elements in a set $A$ that are not in a subset $B$. The inclusion/exclusion rule is presented for finding the number of elements in the union of sets that may overlap.

• Important Theorems and Equations:

  • The Addition Rule: If a finite set $A$ is the union of $k$ distinct, mutually disjoint subsets $A_1, A_2, \dots, A_k$, then $N(A) = N(A_1) + N(A_2) + \dots + N(A_k)$.
  • The Difference Rule: If $A$ is a finite set and $B$ is a subset of $A$, then $N(A - B) = N(A) - N(B)$.
  • The Inclusion/Exclusion Rule for Two Sets: For any finite sets $A$ and $B$, $N(A \cup B) = N(A) + N(B) - N(A \cap B)$.
  • The Inclusion/Exclusion Rule for Three Sets: For any finite sets $A$, $B$, and $C$, $N(A \cup B \cup C) = N(A) + N(B) + N(C) - N(A \cap B) - N(A \cap C) - N(B \cap C) + N(A \cap B \cap C)$.

Section 9.4: The Pigeonhole Principle (pp. 604-617)

• Overview: This section introduces the pigeonhole principle, a fundamental concept stating that if more items than containers are put into the containers, then at least one container must contain more than one item . The section also discusses the generalized pigeonhole principle, which extends this idea . Applications of the principle, including decimal expansions of fractions, are explored.

• Important Theorems and Equations:

  • The Pigeonhole Principle: If $m$ pigeons are placed into $n$ pigeonholes and $m > n$, then at least one pigeonhole contains two or more pigeons .
  • The Generalized Pigeonhole Principle: If $m$ pigeons are placed into $n$ pigeonholes, then at least one pigeonhole contains at least $\lceil \frac{m}{n} \rceil$ pigeons .

Section 9.5: Counting Subsets of a Set: Combinations (pp. 617-634)

• Overview: This section deals with combinations, which are unordered selections of elements from a set. An $r$-combination is a subset of size $r$ chosen from a set of $n$ elements. The order of selection does not matter in combinations. The relationship between permutations and combinations is explained. The section also covers permutations of a set with repeated elements.

• Important Theorems and Equations:

  • Definition of $\binom{n}{r}$ (n choose r): For integers $n$ and $r$ with $0 \le r \le n$, $\binom{n}{r}$ represents the number of subsets of size $r$ that can be chosen from a set with $n$ elements.
  • Formula for Computing $\binom{n}{r}$: $\binom{n}{r} = \frac{P(n, r)}{r!} = \frac{n!}{r!(n-r)!}$
  • Number of Distinguishable Permutations with Repetition: If a collection of $n$ objects has $n_1$ identical objects of type 1, $n_2$ identical objects of type 2, ..., $n_k$ identical objects of type $k$, where $n_1 + n_2 + \dots + n_k = n$, then the number of distinguishable permutations of these $n$ objects is $\frac{n!}{n_1!n_2!n_3! \dots n_k!}$.

Section 9.6: r-Combinations with Repetition Allowed (pp. 634-642)

• Overview: This section extends the concept of combinations to allow for the repetition of elements. An $r$-combination with repetition allowed, or a multiset of size $r$, is an unordered selection of $r$ elements from a set of $n$ elements where elements can be chosen multiple times.

• Important Theorems and Equations:

  • Theorem 9.6.1: The number of $r$-combinations with repetition allowed (or multisets of size $r$) that can be selected from a set of $n$ elements is $\binom{r + n - 1}{r} = \frac{(r + n - 1)!}{r!(n - 1)!}$.

Section 9.7: Pascal’s Formula and the Binomial Theorem (pp. 642-655)

• Overview: This section introduces Pascal’s formula, which provides a recursive relationship between binomial coefficients and forms the basis of Pascal’s triangle. The binomial theorem is a fundamental result that describes the algebraic expansion of powers of a binomial. The section provides both algebraic and combinatorial proofs for these results.

• Important Theorems and Equations:

  • Pascal’s Formula: For integers $n$ and $r$ with $1 \le r \le n$, $\binom{n+1}{r} = \binom{n}{r-1} + \binom{n}{r}$.
  • The Binomial Theorem: For any real numbers $a$ and $b$ and any nonnegative integer $n$, $(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$.

Section 9.8: Probability Axioms and Expected Value (pp. 655-662)

• Overview: This section moves towards a more formal treatment of probability by introducing the axioms of probability. These axioms provide a foundation for deriving additional probability formulas. The concept of expected value of a random variable is also introduced.

• Important Concepts and Equations:

  • Probability Axioms: For a sample space $S$ and a probability function $P$:
    1. For any event $A \subseteq S$, $P(A) \ge 0$.
    2. $P(S) = 1$.
    3. If $A$ and $B$ are mutually disjoint events in $S$, then $P(A \cup B) = P(A) + P(B)$. (This extends to a finite number of mutually disjoint events.)
  • Expected Value (for a discrete random variable X taking values $a_1, a_2, \dots, a_n$ with probabilities $p_1, p_2, \dots, p_n$): $E(X) = a_1p_1 + a_2p_2 + \dots + a_np_n = \sum_{i=1}^{n} a_ip_i$.

Section 9.9: Conditional Probability, Bayes’ Formula, and Independent Events (pp. 662-676)

• Overview: This section introduces conditional probability, which is the probability of an event occurring given that another event has already occurred. Bayes’ theorem provides a way to update probabilities based on new evidence. The concept of independent events, where the occurrence of one event does not affect the probability of the other, is also defined and explored.

• Important Concepts and Equations:

  • Conditional Probability of B given A (where $P(A) > 0$): $P(B|A) = \frac{P(A \cap B)}{P(A)}$.
  • Bayes’ Theorem: If a sample space $S$ is a union of mutually disjoint events $B_1, B_2, \dots, B_n$ with $P(B_i) > 0$ for all $i$, and if $A$ is an event in $S$ with $P(A) > 0$, then for any $k$ ($1 \le k \le n$): $P(B_k|A) = \frac{P(A|B_k)P(B_k)}{P(A)} = \frac{P(A|B_k)P(B_k)}{\sum_{i=1}^{n} P(A|B_i)P(B_i)}$.
  • Independent Events: Events $A$ and $B$ are independent if and only if $P(A \cap B) = P(A)P(B)$.
  • Mutually Independent Events (for three events A, B, and C): $P(A \cap B) = P(A)P(B)$, $P(A \cap C) = P(A)P(C)$, $P(B \cap C) = P(B)P(C)$, and $P(A \cap B \cap C) = P(A)P(B)P(C)$. (Similar conditions apply for more than three events.)a